﻿//本次代码以小堆为例
//#include"heap.h"
//void swap(HPDataType* a1, HPDataType* a2)
//{
//	HPDataType t = *a1;
//	*a1 = *a2;
//	*a2 = t;
//}
////升序，向上
//void Adjustup(HPDataType* a, int child)
//{
//	int parent = (child - 1) / 2;
//	while (child != 0)
//	{
//		if (a[child] < a[parent])
//		{
//			swap(&a[child], &a[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
////升序，向下
//void Adjustdown(HPDataType* a, int n, int parent)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		if (child + 1 < n && a[child + 1] < a[child])
//		{
//			child++;
//		}
//		if (a[child] < a[parent])
//		{
//			swap(&a[child], &a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void Heapcreate(Heap* hp, HPDataType* a, int n)// 堆的构建
//{
//	assert(hp && a && n);
//	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
//	if (!hp->_a)
//	{
//		perror("malloc");
//		exit(-1);
//	}
//	hp->_capacity = hp->_size = n;
//	memcpy(hp->_a, a, sizeof(HPDataType) * n);
//	//进行小堆排序
//	for (int i = 1; i < n; i++)
//	{
//		Adjustup(hp->_a, i);
//	}
//}
//void HeapDestory(Heap* hp)// 堆的销毁
//{
//	assert(hp);
//	free(hp->_a);
//	hp->_a = 0;
//}
//void HeapPush(Heap* hp, HPDataType x)// 堆的插入
//{
//	assert(hp);
//	if (hp->_size == hp->_capacity)
//	{
//		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * (hp->_capacity + 4));
//		if (!hp->_a)
//		{
//			perror("realloc");
//			exit(-1);
//		}
//		hp->_capacity += 4;
//	}
//	hp->_a[hp->_size++] = x;
//	//排序
//	Adjustup(hp, hp->_size - 1);
//}
//void HeapPop(Heap* hp)// 堆的删除
//{
//	assert(hp && hp->_size);
//	hp->_size--;
//}
//HPDataType HeapTop(Heap* hp)// 取堆顶的数据
//{
//	assert(hp);
//	assert(hp->_size);
//	return hp->_a[0];
//}
//int Heapsize(Heap* hp)// 堆的数据个数
//{
//	assert(hp);
//	return hp->_size;
//}
//int HeapEmpty(Heap* hp)// 堆的判空
//{
//	assert(hp);
//	return hp->_size > 0 ? 0 : 1;
//}
//void print(Heap* hp)
//{
//	for (int i = 0; i < hp->_size; i++)
//	{
//		fprintf(stdout, "%d ", hp->_a[i]);
//	}
//	puts("");
//}
//int main()
//{
//	HPDataType a[] = { 1,2,3,9,8,7,4,5,6,0 };
//	Heap hp;
//	Heapcreate(&hp, a, sizeof(a) / sizeof(HPDataType));
//	print(&hp);
//
//	fprintf(stdout, "插入数据后: ");
//	HeapPush(&hp, 10);
//	print(&hp);
//
//	fprintf(stdout, "删除元素后: ");
//	HeapPop(&hp);
//	print(&hp);
//
//	fprintf(stdout, "小堆的堆顶: %d\n", HeapTop(&hp));
//	fprintf(stdout, "小堆的大小: %d\n", Heapsize(&hp));
//
//	if (HeapEmpty(&hp))
//	{
//		puts("此堆为空");
//	}
//	else
//	{
//		puts("此堆不为空");
//	}
//	return 0;
//}

